package 笔试.百度;

import java.util.HashSet;
import java.util.Scanner;

/**
 * @author:谢君臣
 * @Date:2021/9/7-20:15
 * @version:1.0
 * @function:
 */
public class Main03 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < n; i++) {
            function(scanner.nextLine());
        }
    }

    private static void function(String str) {
        char[] chars = str.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (chars[i]=='0'){
                //处理前面的数字
                int j = i-1;
                while (j>=0&&stringBuilder.charAt(j)<'2'){
                    stringBuilder.deleteCharAt(j--);
                }
                if (j<0)i=1;
                else {
                    int temp = stringBuilder.charAt(j)-'1';
                    stringBuilder.deleteCharAt(j);
                    stringBuilder.append(temp);
                    i=j+1;
                }
                // 处理后面的
                while (i<str.length()) {
                    stringBuilder.append(3);
                    i++;
                }
            }else {
                if (chars[i]>'3')stringBuilder.append(3);
                else stringBuilder.append(chars[i]);
            }
        }
        System.out.println(stringBuilder);
    }
}
